package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no30;

import cn.hutool.core.io.FileUtil;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution3 {

    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        String s = "barfoothefoobarman";
        String[] words = {"foo", "bar"};
        s = "aaa";
        words = new String[]{"a", "a"};
//        s = "wordgoodgoodgoodbestword";
//        words = new String[]{"word","good","best","word"};
//        s = "aacbbbbbc";
//        words = new String[]{"aa", "cb"};
//        s = "bcabbcaabbccacacbabccacaababcbb";
//        words = new String[]{"c","b","a","c","a","a","a","b","c"};
        s = FileUtil.readUtf8String("C:\\Users\\tucc38782\\Desktop\\no30.txt");
        words = new String[]{"ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba", "ab", "ba"};
        List<Integer> result = solution.findSubstring(s, words);
        System.out.print(result);
    }

    public List<Integer> findSubstring(String s, String[] words) {
        int length = 0;
        for (String word : words) {
            length += word.length();
        }
        List<Integer> result = new ArrayList<>();
        for(int i = 0;i < s.length();i ++) {
            find(s, i, length, words, words.length, result);
        }
        return result;
    }

    public boolean find(String s, int st, int length, String[] words, int wl, List<Integer> result) {
        if (wl == 0) {
            result.add(st - length);
            return true;
        }
        String lastWords = "";
        for (int i = 0; i < wl; i++) {
            String word = words[i];
            if(word.equals(lastWords)){
                continue;
            }
            lastWords = word;
            if (s.startsWith(word, st)) {
                if(i != wl - 1) {
                    swapWord(words, i, wl - 1);
                }
                boolean find = find(s, st + word.length(), length, words, wl - 1, result);
                if(i != wl - 1) {
                    swapWord(words, wl - 1, i);
                }
                if(find){
                    return true;
                }
            }
        }
        return false;
    }

    public void swapWord(String[] words, int i, int j) {
        String temp = words[i];
        words[i] = words[j];
        words[j] = temp;
    }

}
